Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Maximum Difference Between Node and Ancestor

Problem Statement

Given a root of the binary tree, return the maximum absolute difference in value between any node in a binary tree and its any ancestor.

A node a is the ancestor of node b if node a precedes node b in the path from the root to node b.

Examples

Example 1:

  • Input: root = [5, 3, 8, 0, null, 4, 7, 1]
Image
  • Expected Output: 5
  • Justification: The maximum difference is between node 0 and its ancestor 5, which is 5.

Example 2:

  • Input: root = [2, 1, 3]
Image
  • Expected Output: 1
  • Justification: There are two differences to consider: 2-1 and 3-2. Both differences are 1, so the maximum difference is 1.

Example 3:

  • Input: root = [8, 2, null, 1, 5]
Image
  • Expected Output: 7
  • Justification: The maximum difference is between node 1 and its ancestor 8, which is 7.

Solution

To solve this problem, we adopt a depth-first search (DFS) strategy, exploring each path from the root to the leaf nodes while keeping track of the maximum and minimum values encountered along each path. This approach is effective because it allows us to calculate the difference between the current node and its ancestors' minimum and maximum values in a single traversal, ensuring efficiency and simplicity.

The key is to update the minimum and maximum values as we move down the tree and calculate the difference at each node, comparing it with the global maximum difference found so far. This strategy is chosen for its ability to explore all possible ancestor-descendant pairs without redundant calculations or needing to store additional data structures that represent all ancestors of each node.

Step-by-step Algorithm

  1. Start with the root node of the binary tree, passing the node's value as both the minimum and maximum values encountered so far to a recursive depth-first search (DFS) function.

  2. DFS function:

    • If the current node is null, return the difference between the maximum and minimum values encountered so far on this path.
    • Update the minimum value if the current node's value is less than the current minimum.
    • Update the maximum value if the current node's value is greater than the current maximum.
    • Recursively call the DFS function for the left child of the current node, passing the updated minimum and maximum values.
    • Recursively call the DFS function for the right child of the current node, passing the updated minimum and maximum values.
    • Calculate the maximum difference found in the left and right subtree calls and return it.
  3. Return the result of the DFS call started with the root node, which gives the maximum difference between any node and its ancestor in the binary tree.

Algorithm Walkthrough

Let's consider the input: root = [5, 3, 8, 0, null, 4, 7, 1].

Tree Structure:

The given tree can be visualized as follows:

        5
       / \
      3   8
     /   / \
    0   4   7
   /
  1

Step-by-Step Walkthrough:

  1. Start at the Root (Node 5):

    • Current Node: 5
    • Current Min and Max: Both initialized to the value of the root, which is 5 (min = 5, max = 5).
    • Recursively call DFS on the left child (Node 3).
  2. Move to the Left Child (Node 3):

    • Current Node: 3
    • Update Min and Max:
      • min = min(5, 3) = 3
      • max = max(5, 3) = 5
    • Recursively call DFS on the left child (Node 0).
  3. Move to the Left Child (Node 0):

    • Current Node: 0
    • Update Min and Max:
      • min = min(3, 0) = 0
      • max = max(5, 0) = 5
    • Recursively call DFS on the left child (Node 1).
  4. Move to the Left Child (Node 1):

    • Current Node: 1
    • Update Min and Max:
      • min = min(0, 1) = 0
      • max = max(5, 1) = 5
    • Both left and right children are null:
      • Return the difference max - min = 5 - 0 = 5.
    • Go back to the Node 0.
  5. Node 0 - Right Child is Null:

    • Since the right child of Node 0 is null, the right difference is not calculated.
    • Return the maximum difference obtained from the left subtree: 5.
    • Go back to the Node 3.
  6. Node 3 - Right Child is Null:

    • Since the right child of Node 3 is null, the right difference is not calculated.
    • Return the maximum difference obtained from the left subtree: 5.
    • Go back to the Node 5.
  7. Move to the Right Child (Node 8):

    • Current Node: 8
    • Update Min and Max:
      • min = min(5, 8) = 5
      • max = max(5, 8) = 8
    • Recursively call DFS on the left child (Node 4).
  8. Move to the Left Child (Node 4):

    • Current Node: 4
    • Update Min and Max:
      • min = min(5, 4) = 4
      • max = max(8, 4) = 8
    • Both left and right children are null:
      • Return the difference max - min = 8 - 4 = 4.
    • Go back to the Node 8.
  9. Move to the Right Child (Node 7):

    • Current Node: 7
    • Update Min and Max:
      • min = min(5, 7) = 5
      • max = max(8, 7) = 8
    • Both left and right children are null:
      • Return the difference max - min = 8 - 5 = 3.
    • Go back to the Node 8.
  10. Node 8 - Combine Left and Right Results:

    • Left difference: 4 (from Node 4)
    • Right difference: 3 (from Node 7)
    • Maximum difference for Node 8: max(4, 3) = 4
    • Go back to the Node 5.
  11. Node 5 - Combine Left and Right Results:

    • Left difference: 5 (from Node 3's subtree)
    • Right difference: 4 (from Node 8's subtree)
    • Maximum difference for Node 5: max(5, 4) = 5

Final Output:

  • The maximum difference between a node and its ancestor for the given tree [5, 3, 8, 0, null, 4, 7, 1] is 5.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

: Where N is the number of nodes in the binary tree. The reason for this time complexity is that the depth-first search (DFS) algorithm visits each node exactly once.

Space Complexity

: Where H is the height of the binary tree. This space complexity accounts for the recursive call stack of the DFS traversal. In the worst case, if the binary tree is highly unbalanced, the height of the tree (and thus the maximum depth of the recursive call stack) could be N, making the space complexity .

Maximum Difference Between Node and Ancestor (medium)
Introduction to Root to Leaf Path Pattern
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Step-by-Step Walkthrough:

Final Output:

Code

Complexity Analysis

Time Complexity

Space Complexity